#include <stdio.h>
#include <stdlib.h>

// 带头结点的单链表实现
typedef int ElementType;

typedef struct LNode
{
    ElementType data;
    struct LNode *next;
} LNode, *LinkList;

bool InitList(LinkList &L)
{
    L = (LinkList)malloc(sizeof(LNode));
    if (NULL == L)
    {
        return false;
    }
    L->next = NULL;
    return true;
}

bool DestoryList(LinkList &L)
{
    LNode *node;
    while (L)
    {
        node = L;
        L = L->next;
        free(node);
        node = NULL;
    }
    return true;
}

LNode *GetElem(LinkList L, int i)
{
    if (i < 0)
    {
        return NULL;
    }
    LinkList p = L;
    while (p && i--)
    {
        p = p->next;
    }
    if (!p)
    {
        return NULL;
    }
    return p;
}

bool ListInsert(LinkList &L, int i, ElementType e)
{
    if (i < 1)
    {
        return false;
    }
    LinkList p = GetElem(L, i - 1);
    if (!p)
    {
        return false;
    }
    LinkList node = (LinkList)malloc(sizeof(LNode));
    node->data = e;
    node->next = p->next;
    p->next = node;
    return true;
}

bool ListDelete(LinkList &L, int i, ElementType &e)
{
    if (i < 1)
    {
        return false;
    }
    LinkList p = GetElem(L, i - 1);
    if (!p)
    {
        return false;
    }
    if (!p->next)
    {
        return false;
    }
    LinkList node = p->next;
    e = node->data;
    p->next = node->next;
    free(node);
    return true;
}

LNode *LocateElem(LinkList L, ElementType e)
{
    LNode *p = L->next;
    while (p && p->data != e)
    {
        p = p->next;
    }
    return p;
}

int Length(LinkList L)
{
    int len = 0;
    LNode *p = L->next;
    while (p)
    {
        p = p->next;
        len++;
    }
    return len;
}

void PrintList(LinkList L)
{
    LNode *p = L->next;
    while (p)
    {
        printf("%3d", p->data);
        p = p->next;
    }
    printf("\n");
}

bool Empty(LinkList L)
{
    return NULL == L->next;
}

bool reverseList(LinkList &L)
{
    if (L->next == NULL)
    {
        return true;
    }
    LNode *head = L, *cur = L->next;
    head->next = NULL;
    LNode *next;
    while (cur)
    {
        next = cur->next;
        cur->next = head->next;
        head->next = cur;
        cur = next;
    }
    return true;
}

int main()
{
    int elem;
    LinkList L;
    InitList(L);
    while (scanf("%d", &elem))
    {
        if (elem == 9999)
        {
            break;
        }
        ListInsert(L, 1, elem);
    }
    PrintList(L);
    printf("L:len = %d\n", Length(L));
    ListDelete(L, 5, elem);
    PrintList(L);
    printf("Element next data is %d\n", LocateElem(L, 6)->next->data);
    reverseList(L);
    PrintList(L);
    return 0;
}